Претрага у дубину и ширину

Често се у склопу проблема разматра одређен скуп поља таквих да се са једног поља може прећи на друго. На пример, простор се може поделити на матрицу поља и са сваког поља се може прећи на 4 или на 8 суседних поља. Даље, на пример, скуп градова се може представити пољима и са поља на поље се може прећи ако постоји директан пут између одговарајућих градова. Поља могу бити, на пример, стања током играња неке игре (на пример, распореди фигура на шаховској табли) и са једног поља се може прећи на друго ако постоји исправан потез играча који нас из једног стања доводи у друго. Овакви проблеми се често репрезентују структуром података која се назива граф и који је представљен скупом поља (тзв. чворова) и веза између њих (тзв. грана). Један од основних задатака приликом решавања описаних проблема је да се просто обиђу сва поља до којих се може стићи ако се крене из неког полазног поља. То се најчешће остварује помоћу алгоритма претраге у дубину и алгоритма претраге у ширину. У наставку ће бити приказано неколико проблема у којима се ови алгоритми примењују на решавање проблема у којима су поља и прелази између њих представљени имплицитно (не користе се графови).